'-----------------------------------------------------------------------------
'---------------------------- SIMPLE DUNGEON GENERATOR -----------------------
'-----------------------------------------------------------------------------

'PURPOSE: Generate simple dungeons for use in Rogue-like games.

'DATE: MARCH 2011

'LICENSE: Public Domain

'-----------------------------------------------------------------------------


'**** MOJO-BASED EXAMPLE *****

Strict



'*****************************************



'----- DUNGEON CODE ----------------------------------------


'Do NOT change the AREA_ID_ constant values.
'Generated area ids will always be greater than zero.
Const AREA_ID_PERIMETER:Int = -2
Const AREA_ID_UNASSIGNED:Int = -1				
Const AREA_ID_CORRIDOR:Int = 0					

'Currently three density levels are available.
Const DENSITY_LOW:Int = 0
Const DENSITY_MEDIUM:Int = 1
Const DENSITY_HIGH:Int = 2


'Barrier ID values should be less than zero
Const OBJ_ID_KEY:Int = -7
Const OBJ_ID_STAR:Int = -6
Const OBJ_ID_RUBBLE:Int = -5
Const OBJ_ID_DOOR_LOCKED:Int = -4
Const OBJ_ID_DOOR_CLOSED:Int = -3
Const OBJ_ID_WALL_PERIMETER:Int = -2
Const OBJ_ID_WALL:Int = -1


'Non-barrier obj ID values should be greater than zero
Const OBJ_ID_VOID:Int = 0
Const OBJ_ID_DOOR_OPEN:Int = 1


Class Dungeon

	'The dimensions of the dungeon are represented by columns and rows.
	Field sizeCols:Int, sizeRows:Int
			
	'See below...						
	Field areaIDGrid:Int[]		
	
	'areaIDGrid stores the integer ID values of generated areas (>0), generated connections (0)
	'unassigned (-1) and perimeter (-2) coordinates.
	'10x10 example with two areas joined by a single connection (of two corridors):
	' -2 -2 -2 -2 -2 -2 -2 -2 -2 -2
	' -2 -1 -1 01 01 01 01 -1 -1 -2
	' -2 -1 -1 01 01 01 01 -1 -1 -2
	' -2 -1 -1 01 01 01 01 -1 -1 -2
	' -2 -1 -1 -1 -1 -1 00 -1 -1 -2
	' -2 -1 -1 -1 -1 -1 00 -1 -1 -2
	' -2 02 02 02 -1 -1 00 -1 -1 -2
	' -2 02 02 02 00 00 00 -1 -1 -2
	' -2 02 02 02 -1 -1 -1 -1 -1 -2
	' -2 -2 -2 -2 -2 -2 -2 -2 -2 -2
	
	'See below...
	Field objIDGrid:Int[]
	
	'objIDGrid stores the integer ID values of placed objects (eg doors, rubble, void, walls, etc.)
	'The principle is the same as for areaIDGrid.
	
	
	Method New(cols:Int, rows:Int)
	
		sizeCols = cols
		sizeRows = rows
		areaIDGrid = New Int[sizeCols * sizeRows]
		objIDGrid = New Int[sizeCols * sizeRows]
		ResetGrids

	End
	
	
	Method ResetGrids:Void()
	
		'Reset NON-perimeter coordinates
		For Local r:Int = 1 Until sizeRows - 1
			For Local c:Int = 1 Until sizeCols - 1
				areaIDGrid[(r * sizeCols) + c] = AREA_ID_UNASSIGNED
				objIDGrid[(r * sizeCols) + c] = OBJ_ID_WALL
			Next
		Next
	
		'Reset perimeter coordinates
		For Local c:Int = 0 Until sizeCols
			areaIDGrid[(0 * sizeCols) + c] = AREA_ID_PERIMETER
			areaIDGrid[((sizeRows - 1) * sizeCols) + c] = AREA_ID_PERIMETER
			objIDGrid[(0 * sizeCols) + c] = OBJ_ID_WALL_PERIMETER
			objIDGrid[((sizeRows - 1) * sizeCols) + c] = OBJ_ID_WALL_PERIMETER
		Next 
	
		For Local r:Int = 0 Until sizeRows
			areaIDGrid[(r * sizeCols) + 0] = AREA_ID_PERIMETER
			areaIDGrid[(r * sizeCols) + (sizeCols - 1)] = AREA_ID_PERIMETER
			objIDGrid[(r * sizeCols) + 0] = OBJ_ID_WALL_PERIMETER
			objIDGrid[(r * sizeCols) + (sizeCols - 1)] = OBJ_ID_WALL_PERIMETER
		Next
	
	End
	
	
	'Generate a number of areas (calculated from the 'density' parameter)
	'and establish connections between them.
	Method GenerateAreas:Void(density:Int)
	
		Local areas:Location[]
		Local tryNumAreas:Int = 0
		Local numAreas:Int = 0

		Select density
		
			Case DENSITY_LOW
				tryNumAreas = 1 + Floor(sizeCols * sizeRows * 0.0025)       
			
			Case DENSITY_MEDIUM
				tryNumAreas = 1 + Floor(sizeCols * sizeRows * 0.005)
			
			Case DENSITY_HIGH
				tryNumAreas = 1 + Floor(sizeCols * sizeRows * 0.05)
					
		End			
				
		'VVVV AREA GENERATION VVVV		
					
		areas = New Location[tryNumAreas]
		
		For Local id:Int = 1 To tryNumAreas		
			
			Local areaCols:Int
			Local areaRows:Int
			
			Local c:Int, r:Int
			
			Local loopCount:Int = 0
			Local overlap:Bool = False
			
			Repeat
				'Generate a randomly-dimensioned area at a random coodinate.
				'Check that it doesn't overlap an existing area.
				'If it does overlap then discard it and try again
				'until a non-overlapping area has been generated.
				
				areaCols = Floor(Rnd(2, Floor(sizeCols / 4)))
				areaRows = Floor(Rnd(2, Floor(sizeRows / 4)))
				c = Floor(Rnd(1, sizeCols - areaCols))
				r = Floor(Rnd(1, sizeRows - areaRows))
				
				overlap = CheckAreaOverlap(c, r, areaCols, areaRows)
				
				'If a non-overlapping area hasn't been generated after a
				'reasonable number of attempts then abandon this loop iteration.
				loopCount += 1
				If loopCount > 1000 Then Exit		
				
			Until (Not overlap)
		
			If (Not overlap) 
				numAreas += 1
				MakeArea numAreas, c, r, areaCols, areaRows
				areas[numAreas - 1] = New Location(numAreas, c, r, areaCols, areaRows)
			Endif
		
		Next
	
		'numAreas is the actual number of generated areas, NOT tryNumAreas, 
		'so resize the array accordingly.
		areas = areas[..numAreas]
		
		'VVVV AREA CONNECTION GENERATION VVVV
		
		'Shuffle areas
		For Local n:Int = 1 To numAreas
			Local i:Int = Floor(Rnd(0, areas.Length))
			Local j:Int = Floor(Rnd(0, areas.Length))
			Local swap:Location = areas[i]
			areas[i] = areas[j]
			areas[j] = swap
		Next
	
		'Create a connection between areas in shuffled sequence to ensure
		'every area is reachable, either directly or indirectly.
		For Local i:Int = 0 Until areas.Length - 1
			MakeConnection(areas[i], areas[i + 1])
		Next
	
	
		'VVVV BARRIER GENERATION VVVV
		
		Local rubbleChance:Int = 2					'<- Probably need to make this a parameter of this method or a field/property of this class.
				
		For Local r:Int = 1 Until sizeRows - 1
			For Local c:Int = 1 Until sizeCols - 1
			
				'Check for an appropriate location along a row.
				If (areaIDGrid[(r * sizeCols) + c] = AREA_ID_CORRIDOR) And
				  (areaIDGrid[((r - 1) * sizeCols) + c] = AREA_ID_UNASSIGNED) And
					(areaIDGrid[((r + 1) * sizeCols) + c] = AREA_ID_UNASSIGNED)
					
						'Closed doors beside an area.
						If (areaIDGrid[(r * sizeCols) + (c - 1)] > 0) Or (areaIDGrid[(r * sizeCols) + (c + 1)] > 0)		
							objIDGrid[(r * sizeCols) + c] = OBJ_ID_DOOR_CLOSED
						Else 
							'A percent chance to place Rubble in a corridor.
							If Floor(Rnd(0, 100)) <= rubbleChance Then objIDGrid[(r * sizeCols) + c] = OBJ_ID_RUBBLE
			
						Endif

				Endif
				
				'Check for an appropriate location along a column.
				If (areaIDGrid[(r * sizeCols) + c] = AREA_ID_CORRIDOR) And
				  (areaIDGrid[(r * sizeCols) + (c - 1)] = AREA_ID_UNASSIGNED) And
					(areaIDGrid[(r * sizeCols) + (c + 1)] = AREA_ID_UNASSIGNED)
					
						'Closed doors beside an area.
						If (areaIDGrid[((r - 1) * sizeCols) + c] > 0) Or (areaIDGrid[((r + 1) * sizeCols) + c] > 0)		
							objIDGrid[(r * sizeCols) + c] = OBJ_ID_DOOR_CLOSED
						Else 
							'A percent chance to place Rubble in a corridor.
							If Floor(Rnd(0, 100)) <= rubbleChance Then objIDGrid[(r * sizeCols) + c] = OBJ_ID_RUBBLE
						Endif

				Endif
				
			Next
		Next
		
		
		'Locked doors are placed near areas that only have a single entry.

		For Local area := Eachin areas
		
			Local entry:Location = Null
			Local entryCount:Int = 0
			
			Local c:Int, r:Int
		
			For c = (area.col - 1) Until (area.col + area.width)
		
				r = area.row - 1
				If (areaIDGrid[(r * sizeCols) + c] = AREA_ID_CORRIDOR)
					entryCount += 1
					If (entry = Null) Then entry = New Location(area.id, c, r)
				Endif
				
				r = area.row + area.height
				If (areaIDGrid[(r * sizeCols) + c] = AREA_ID_CORRIDOR)
					entryCount += 1
					If (entry = Null) Then entry = New Location(area.id, c, r)
				Endif
				
			Next
		
			For r = (area.row - 1) Until (area.row + area.height)
			
				c = area.col - 1
			
				If (areaIDGrid[(r * sizeCols) + c] = AREA_ID_CORRIDOR)
					entryCount += 1
					If (entry = Null) Then entry = New Location(area.id, c, r)
				Endif
				
				c = area.col + area.width

				If (areaIDGrid[(r * sizeCols) + c] = AREA_ID_CORRIDOR)
					entryCount += 1
					If (entry = Null) Then entry = New Location(area.id, c, r)
				Endif
				
			Next
	
			If entryCount = 1 Then objIDGrid[(entry.row * sizeCols) + entry.col] = OBJ_ID_DOOR_LOCKED

		Next
	
	End
		
		
	'Check if a proposed area will overlap an existing area.
	Method CheckAreaOverlap:Bool(c:Int, r:Int, cols:Int, rows:Int)
	
		For Local r1:Int = (r - 1) Until (r + rows + 1)
			For Local c1:Int = (c - 1) Until (c + cols + 1)
				If areaIDGrid[(r1 * sizeCols) + c1] > 0 Then Return True		'Overlap.
			Next
		Next
		
		Return False	'No overlap.
		
	End
		
		
	'Set all areaIDGrid coordinates to the new area's id value.
	'Also set corresponding obj ids to void.
	Method MakeArea:Void(id:Int, c:Int, r:Int, cols:Int, rows:Int)

		For Local r1:Int = r Until (r + rows)
			For Local c1:Int = c Until (c + cols)
				areaIDGrid[(r1 * sizeCols) + c1] = id
				objIDGrid[(r1 * sizeCols) + c1] = OBJ_ID_VOID
			Next
		Next

	End
	
	
	'Connect one area to another using either one or two 'corridors', as required.
	Method MakeConnection:Void(areaA:Location, areaB:Location)
	
		'Select a random coordinate within each area.
		Local c1:Int = Floor(Rnd(areaA.col, (areaA.col + areaA.width - 1)))
		Local r1:Int = Floor(Rnd(areaA.row, (areaA.row + areaA.height - 1)))
		Local c2:Int = Floor(Rnd(areaB.col, (areaB.col + areaB.width - 1)))
		Local r2:Int = Floor(Rnd(areaB.row, (areaB.row + areaB.height - 1)))
		
		'Calculate the distances between the coordates.
		Local cdist:Int = Abs(c1 - c2) + 1
		Local rdist:Int = Abs(r1 - r2) + 1
		
		'Make west<->east corridor if necessary.
		If (c1 < c2) 'areaA's random coordinate column is west of areaB's random coordinate column
			MakeCorridor c1, r1, cdist, 1
			c1 += cdist
		Else 'areaA's random coordinate column is east of areaB's random coordinate column
			MakeCorridor c2, r2, cdist, 1
			c2 += cdist
		Endif
		
		'Make north<->south corridor if necessary.
		If (r1 < r2) Then MakeCorridor c1, r1, 1, rdist Else MakeCorridor c2, r2, 1, rdist

	End
				
				
	'Set areaIDGrid coordinates to AREA_ID_CORRIDOR value along a corridor, but only if they
	'are not yet assigned an id > 0.	(This allows area IDs to be fully preserved in the grid).
	'Also set corresponding obj ids to void.
	Method MakeCorridor:Void(c:Int, r:Int, cols:Int, rows:Int)

		For Local r1:Int = r Until (r + rows)
			For Local c1:Int = c Until (c + cols)
				If (areaIDGrid[(r1 * sizeCols) + c1] < 0) 
					areaIDGrid[(r1 * sizeCols) + c1] = AREA_ID_CORRIDOR
					objIDGrid[(r1 * sizeCols) + c1] = OBJ_ID_VOID
				Endif
			Next
		Next

	End				
	
			
	'Return a 'Rogue-like' string representation of the dungeon.
	Method GetString:String()
	
		Local str:String
	
		For Local r:Int = 0 Until sizeRows
		
			For Local c:Int = 0 Until sizeCols
				
				Select objIDGrid[(r * sizeCols) + c]
				
					Case OBJ_ID_VOID
						str += "."
			
					Case OBJ_ID_WALL
						str += "#"
						
					Case OBJ_ID_WALL_PERIMETER
						str += "X"
						
					Case OBJ_ID_DOOR_CLOSED
						str += "+"
						
					Case OBJ_ID_DOOR_OPEN
						str += "'"
			
					Case OBJ_ID_DOOR_LOCKED
						str += "%"
		
					Case OBJ_ID_RUBBLE
						str += "|"
					
				End

			Next
			
			str += "~n"
			
		Next
	
		Return str
	
	End


End


'---- COMPANION CLASS(ES)

'Currently only used in the area generation methods of the Dungeon class.
Class Location

	'Location information - for a whole area or a single coordinate.

	Field id:Int
	Field col:Int, row:Int
	Field width:Int, height:Int


	Method New(i:Int, c:Int, r:Int, w:Int, h:Int)
	
		id = i
		col = c
		row = r
		width = w
		height = h
	
	End


	Method New(i:Int, c:Int, r:Int)
	
		id = i
		col = c
		row = r
		width = 1
		height = 1
	
	End


End



